#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "../quicksort.h"

#define PAGE_SIZE 4096

// Estrutura de uma árvore binária
typedef struct stt_tree {
    int *local;
    struct stt_tree *filho_esq;
    struct stt_tree *filho_dir;
} arvore_b;

// Varáveis globais
int k;                  // Dimensão do problema
int n_nivel;            // Nível do problema quase sequencial
int **repr;             // Para armazenar a representação da árvore
int **repr_i;
int tam_repr;           // Tamanho do vetor de representação
int iter;               // Quantidade de iterações
extern HLRC_myself;     // Número do processo atual
extern HLRC_nprocs;     // Quantidade de processos executando
extern HLRC_nlocks;
extern HLRC_init_flag;
#define NLOCKS          (18*1024)

int mem_alloc (int size) {
    unsigned int address, modulo;
    address = (unsigned int) HLRC_Malloc(size + PAGE_SIZE);
    modulo  = address % PAGE_SIZE;
    if (modulo != 0)
        address += PAGE_SIZE - modulo;
    return address;
}


// Função principal que constrói uma KD Tree
void kdtree(int **p, int profundidade, int n_pontos, int indice, int iter_local) {
    
    int i;
    
    if (!p[0])
        return;
    
    // Selecionando o eixo baseado na profundade tal que o eixo circule em
    // torno de todos os valores válidos.
    int eixo;
    eixo = profundidade % k;
    
    // Ordena a lista de pontos
    quick_sort(p, 0, n_pontos-1, eixo);
    
    // Escolhe o ponto médio como o elemento pivo
    int meio;
    meio = n_pontos / 2;
    
    int caminho;    // Para determinar o caminho da recursão ate o nível correto
    int casa;       // Casa decimal usada na fórmula para calcular o caminho
    casa = pow(2, (n_nivel-1-profundidade));
    caminho = HLRC_myself & casa;
    
    // Determina pontos que vão à direita e à esquerda da árvore
    int **pontos_esq = NULL;
    int **pontos_dir = NULL;
    
    // Cria o no e constrói as sub-árvores
    arvore_b *no;
    no = (arvore_b*) malloc(sizeof(arvore_b));
    
    // Recupera o valor mediano para inserir no nó atual
    int *valor_meio = malloc(sizeof(int) * k);
    for (i=0; i<k; i++)
        valor_meio[i] = p[meio][i];
    
    // Inserindo dados nas representações da árvore
    for (i=0; i<k; i++)
        //if (iter_local != iter)
            repr[indice][i] = valor_meio[i];
        //else
        //    repr_i[indice][i] = valor_meio[i];
    
    // Determina se terá recursão à esquerda
    if (!caminho || profundidade >= n_nivel) {
        // Gerando uma nova lista de pontos
        pontos_esq = malloc(sizeof(int*) * meio+1);
        i = 0;
        while (i < meio) {
            pontos_esq[i] = malloc(sizeof(int) * k);
            memcpy(pontos_esq[i], p[i], sizeof(int) * k);
            i++;
        }
        pontos_esq[i] = NULL;
    }
    
    // Determina se terá recursão à direita
    if (caminho || profundidade >= n_nivel) {
        pontos_dir = malloc(sizeof(int*) * (n_pontos-meio+1));
        i = 0;
        while (i < n_pontos-meio-1) {
            pontos_dir[i] = malloc(sizeof(int*) * k);
            memcpy(pontos_dir[i], p[i+meio+1], sizeof(int) * k);
            i++;
        }
        pontos_dir[i] = NULL;
    }
    
    // Desalocando memória referente aos pontos
    for(i = 0; i < n_pontos-1; i++)
        free(p[i]);
    free(p);
    
    // Chamando recursão para esquerda
    if (!caminho || profundidade >= n_nivel)
        kdtree(pontos_esq, profundidade+1, meio, 2*indice, iter_local);
    // Chamando recursão para esquerda
    if (caminho || profundidade >= n_nivel)
        kdtree(pontos_dir, profundidade+1, n_pontos-meio-1, 2*indice+1, iter_local);
}

arvore_b* monta() {
    int i;
    arvore_b** resposta;
    resposta = (arvore_b**) malloc(sizeof(arvore_b*) * tam_repr);
    for (i=1; i<=tam_repr; i++) {
        resposta[i] = (arvore_b*) malloc(sizeof(arvore_b));
        resposta[i]->local = repr[i];
    }
    for (i=1; i<=tam_repr/2; i++) {
        resposta[i]->filho_esq = resposta[i*2];
        resposta[i]->filho_dir = resposta[i*2+1];
    }
    return resposta[1];
}

main(int argc, char **argv) {
   
    // Inicialização do HLRC
    HLRC_Init(argc, argv);
    
    int n_pontos = atoi(argv[3]);   // Número de pontos retirados do arquivo
    
    // Aloca toda a memória necessária
    float res = log(n_pontos) / log(2);
    if (res == (int)res)
        tam_repr = (1 << (((int) res )));
    else
        tam_repr = (1 << (((int) res ) + 1));
    
    int i, j;
    
    if (HLRC_myself == 0) {
        repr = (int**) mem_alloc(sizeof(int*) * tam_repr);
        for (i=1; i<=tam_repr; i++)
            repr[i] = (int*) mem_alloc(sizeof(int) * k);
    }
    
    // Inicia o paralelismo
    HLRC_InitParallel();
    
    // Inicia as estatísticas
    HLRC_Reset();
    
    // Zera o buffer
    for (i=0; i<tam_repr; i++) {
        for (j=0; j<k; j++)
            repr[i][j] = -1;
    }
    
    int **pontos;
    k = atoi(argv[1]);              // Tamanho da dimensão
    iter = atoi(argv[2]);           // Iterações
    
    pontos = malloc(sizeof(int*) * n_pontos + 1);
    
    // Lendo cada linha da entrada e atribuindo os valores
    srand(10);
    int ponto[k];
    for (i=0; i<n_pontos; i++) {
        for(j=0; j < k-1; j++)
            ponto[j] = rand() % 1000;
        ponto[j] = rand() % 1000;
        pontos[i] = malloc(sizeof(int) * k);
        for (j=0; j<k; j++) 
            pontos[i][j] = ponto[j];
    }
    pontos[i] = NULL;
    
    // Calcula o tamanho do caminho de cada nó até executar independentemente
    int q = HLRC_nprocs;
    n_nivel = 0;
    while (!(q & 1)) {
        n_nivel++;
        q >>= 1;
    }
    
    // representação local
    repr_i = (int**) mem_alloc(sizeof(int*) * tam_repr);
    for (i=1; i<=tam_repr; i++)
        repr_i[i] = (int*) mem_alloc(sizeof(int) * k);
    
    int w;
    // Inicia programa computação do problema
    for (w=0; w<=iter; w++) {
        if ((w % HLRC_nprocs) == HLRC_myself) {
            printf("np %d\n", HLRC_nprocs);
            kdtree(pontos, 0, n_pontos, 1, w);
            
            //if (w < iter && HLRC_myself == 0) {
            //    for (i=0; i<=tam_repr; i++)
            //        free(repr_i[i]);
            //}
        }
    }
    
    // Aguarda todos os processos para gerar a árvore
    HLRC_Barrier();
    
    // Monta a árvore
    
    if (HLRC_myself == 0) {
        arvore_b *tree;
        tree = monta();
        
        printf("(%d, %d, %d)\n", tree->local[0], tree->local[1], tree->local[2]);
        printf("(%d, %d, %d)\n", tree->filho_esq->local[0], tree->filho_esq->local[1], tree->filho_esq->local[2]);
        printf("(%d, %d, %d)\n", tree->filho_dir->local[0], tree->filho_dir->local[1], tree->filho_dir->local[2]);
    }
    
    // Aguarda todos os processos para finalizar o programa
    HLRC_Barrier();
    
    // Finaliza a coleta de estatísticas
    if (HLRC_myself == 0)
        HLRC_ClockStop();
    
    // Finaliza o processamento paralelo
    HLRC_End();
}